import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/22 9:04
 * @description 队列维护空位置
 */
public class Solution {
    public static void main(String[] args) {

    }
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        for (int i = 0; i < m; i++) {
            // 维护空位置
            Queue<Integer> q = new LinkedList<>();
            // 从右往左遍历
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '*') {
                    // 遇到障碍物，清空队列
                    q.clear();
                }else if (box[i][j] == '#') {
                    if (!q.isEmpty()) {
                        // 队列不为空，存在空位置，那么石头会掉落
                        int pos = q.poll();
                        box[i][pos] = '#';
                        box[i][j] = '.';
                        // 石头下落后，j位置变成空位，加入队列
                        q.add(j);
                    }
                }else {
                    // 遇到空位
                    q.add(j);
                }
            }
        }
        char[][] ans = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[j][m-i-1] = box[i][j];
            }
        }
        return ans;
    }
}
